package algorithm.sort;

public class QuickSort extends Common implements Sort {
    public QuickSort(ImplementType type) {
        super(type);
    }

    @Override
    public void execute(int[] nums) {
        execute(nums, type);
    }

    // 当nums值相同时，数量超过10W 会出现StackOverflowError错误
    public void quickSort(int nums[], int left, int right) {
        if ((right - left) < 1) {
            return;
        }
        int k = nums[left];
        int sl = left;
        int sr = right;
        while (left < right) {
            for (; left < right && nums[right] >= k; right--)
                ;
            if (left < right) {
                nums[left] = nums[right];
            }
            for (; left < right && nums[left] <= k; left++)
                ;
            if (left < right) {
                nums[right] = nums[left];
            }
            if (left == right) {
                nums[left] = k;
                break;
            }
        }
        quickSort(nums, sl, right - 1);
        quickSort(nums, left + 1, sr);
    }
    
    //涉及的计算太多，导致速度下降,效率低的一匹
    public void quickSort(int[] nums) {
        if (nums.length < 2) {
            return;
        }
        int left = 0;
        int right = nums.length - 1;
        int mod = 10000007;
        int[] queue = new int[mod];
        int rear = 0;
        int front = 0;
        int sr;
        int sl;
        int k;
        queue[front++] = left;
        queue[front++] = right;
        while (rear != front) {
            left = queue[rear++];
//            rear %= mod;
            right = queue[rear++];
//            rear %= mod;
            k = nums[left];
            sl = left;
            sr = right;
            while (left < right) {
                for (; left < right && nums[right] >= k; right--)
                    ;
                if (left < right) {
                    nums[left] = nums[right];
                }
                for (; left < right && nums[left] <= k; left++)
                    ;
                if (left < right) {
                    nums[right] = nums[left];
                }
                if (left == right) {
                    nums[left] = k;
                    break;
                }
            }
            if (sl < (right - 1)) {
                queue[front++] = sl;
//                front %= mod;
                queue[front++] = right - 1;
//                front %= mod;
            }
            if ((left + 1) < sr) {
                queue[front++] = left + 1;
//                front %= mod;
                queue[front++] = sr;
//                front %= mod;
            }
        }
    }

    @Override
    public void execute(int[] nums, ImplementType methodType) {
        this.type = methodType;
        switch (methodType) {
        case DEFAULT:
        case DFS:
            quickSort(nums, 0, nums.length - 1);
            break;
        case BFS:
            quickSort(nums);
        default:
            break;
        }
    }
}
